package easy;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class leetcode20_IsValid {
    public static void main(String[] args) {
        System.out.println(isValid("{[}]"));

    }

    /*给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
        有效字符串需满足：
            左括号必须用相同类型的右括号闭合。
            左括号必须以正确的顺序闭合。
            每个右括号都有一个对应的相同类型的左括号。
    */

    // 思路：匹配对应的括号 类似于栈 进栈和出栈的过程
    // 定义一个哈希表 存储用于匹配的括号
    private static final Map<Character, Character> map = new HashMap<Character, Character>() {{
        put('{', '}');
        put('[', ']');
        put('(', ')');
        put('?', '?');
    }};

    public static boolean isValid(String s) {
        // 判断字符串是否为空 如为空则返回false
        // containsKey(Key) 方法用于判断哈希表中是否有这个键 无 则返回false， 有 则返回true
        if (s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        // 定义一个链表
        LinkedList<Character> stack = new LinkedList<Character>() {{
            // 防止栈下界溢出
            add('?');
        }};
        // 遍历字符串
        // String.toCharArray()方法 用于将字符串转换为字符数组char[]
        for (Character c : s.toCharArray()) { // "{[()]}"
            // 判断字符串中的每个字符是否在对应的哈希表中
            // 如果在 则将改字符添加到链表的末尾（进栈）
            if (map.containsKey(c)) stack.addLast(c);
            // removeLast()删除并返回链表的最后一个元素(出栈)
            // map.get(Key)用于获取对应键的值
            // 当获取的对应的值
            else if (map.get(stack.removeLast()) != c) return false;
        }
        // 当栈内元素为空时 返回
        return stack.size() == 1;
    }
}

